﻿# -*- coding: utf-8 -*-
import time
import random
import argparse

def elapse(func, *args):
    """计算执行func花费的时间"""
    start = time.clock()
    res = func(*args)
    elapse = ("%.6fs" %
        (time.clock() - start))
    return res, elapse

def arg_parse():
    parser = argparse.ArgumentParser()
    parser.add_argument("n", type=int,
        help=u"生成数组的长度")
    parser.add_argument("-g","--gen_output",
        action="store_true",
        help=u"只生成数组，不运算")
    parser.add_argument("-v","--verbose",
        action="store_true",
        help=u"显示更多信息标记")
    args = parser.parse_args()
    return args.n, args.gen_output, args.verbose

"""
找出数组中唯一的重复元素

描述
将1~n的n个数放在包含n+1个元素的数组中，
只有唯一的一个元素重复，其它均只出现一次，
设计算法求解这一唯一重复的元素。
要求
每个数组元素只能访问一次，空间复杂度为O(1)
"""

def makeInput(n):
    """构造数组，包含唯一的重复元素
    数组包含1~n，长度是n+1
    """
    list = range(1, n+1)
    x = random.randint(1,n)
    list.append(x)
    random.shuffle(list)
    return list

def printList(list):
    print len(list)
    for e in list:
        print e,

"""
n = 1000001
(method,time,result):
1 0.148561s 353855
2 0.166781s 353855
4 0.167987s 353855
3 0.123925s 353855
n = 1000001
(method,time,result):
1 0.151085s 289056
2 0.167354s 289056
4 0.015654s 289056
3 0.014601s 289056

n = 10000001
(method,time,result):
1 1.808690s 2903793
2 1.934355s 2903793
4 2.016767s 2903793
3 1.261412s 2903793
n = 10000001
"""
def findRepeat_1(list):
    """解法一
    数组求和减去1~n的和
    缺点：当n很大时会出现溢出
    """
    sum = 0
    for e in list:
        sum += e
    #or use reduce, but slow than for loop
    #sum = reduce(lambda x, y: x+y, list)
    return sum - len(list)*(len(list)-1)/2

def findRepeat_2(list):
    """解法二
    数组异或的结果和1~n异或的结果计算异或
    """
    r = 0
    for i,e in enumerate(list):
        r ^= e^i
    return r

def findRepeat_3(list):
    """解法三
    将数组取值操作看做有向图中的一条边，
    索引为边的前驱，值为边的后继
    可以得出结论：0只有后继没有前驱，
    其他数字既有后继也有前驱，
    重复的那个数字有两个前驱。
    从0开始沿着有向图的边往前遍历节点，
    这样必然会有一个节点是已经访问过的节点
    这个节点的前驱或索引就是重复的数字
    解法三和四都是使用这个思路。
    解法三使用对元素取负做标记来实现
    10000001 3.113108s
    10000001 0.647919s
    运算时间很不稳定
    """
    i = 0
    while True:
        if list[i] < 0:
            break
        list[i] = -list[i]
        i = -list[i]
    return i

def findRepeat_4(list):
    """解法四
    思路同解法三
    不使用标记，而是使用两个步进不同的
    下标来访问，在有环的图中一定会相遇
    s步进一次，f步进两次，
    相遇时，由于步进的关系和有向图的环的存在
    可以得到f走的距离是s的两倍以及f走的距离等于
    s的距离加环的总长度，因此可以将f设为0，
    s和f同时步进，当再次相遇时，相遇点一定是相同的数字
    """
    s,f = 0,0
    while True:
        s = list[s]
        f = list[list[f]]
        if s == f:
            break
    f = 0
    while True:
        s = list[s]
        f = list[f]
        if s == f:
            break
    return s

def main(n, g, V):
    list = makeInput(n)
    #list = [8,5,7,4,2,3,1,6,9,4]
    if g:
        printList(list)
    else:
        if V and len(list) <= 50:
            print "array= ", list
        print "n =", len(list)
        print "(method,time,result):"
        res = elapse(findRepeat_1, list)
        print "1", res[1], res[0]
        res = elapse(findRepeat_2, list)
        print "2", res[1], res[0]
        res = elapse(findRepeat_4, list)
        print "4", res[1], res[0]
        res = elapse(findRepeat_3, list)
        print "3", res[1], res[0]

if __name__ == "__main__":
    main(*arg_parse())